package com.sise.DP;

/**
 *      72. 编辑距离
 *
 *      题解：
 *          1、状态：题目提供的字符串长度
 *          2、选择：选择 替换、删除、新增。这里应该站在 dp[][] 数组从小到大的思想进行考虑
 *          3、状态转移方程：转化为当前位置有三种可能，那就是 替换、删除、新增。我们需要进行比较后选择 最小的步数
 *          4、base case
 *
 *          dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数 (由小到大)
 *          dp[][] 数组的定义也是 题目中所要求的返回值，base case 则是边界情况
 *
 *
 *          对“dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。”的补充理解：
 *          以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，
 *          也就是将 horse 转换为 ros，因此有：
 *          (1) dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，
 *              然后将第五个字符 word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）
 *          (2) dp[i][j-1]，原本 word[0..i] 到 word2[0..j-1] 的步数已经知道，此时我们要扩展为 dp[i][j]，那么就多了 word2[j] 一步，
 *              故此，word1 就需要插入一位数，所以为 dp[i][j] = dp[i][j-1] + 1(新增)
 *          (3) dp[i-1][j]，原本 word[0..i-1] 到 word2[0..j] 的步数已经知道，此时我们要扩展为 dp[i][j]，那么就多了 word1[i] 一步，
 *              故此，word1 就需要删除第 i 位数，所以 dp[i][j] = dp[i - 1][j] + 1(删除)
 */
public class _72_minDistance {
    public int minDistance(String word1, String word2) {

        int rows = word1.length();
        int cols = word2.length();

        int[][] dp = new int[rows + 1][cols + 1];       // 要在原有长度上 +1，因为 dp[0][0] 放置长度为 0 的数值

        for (int i = 1; i <= rows; i++) {               // 第一列，word2为空时，word1 转为 word2 的步数，一直删除
            dp[i][0] = i;
        }
        for (int j = 1; j <= cols; j++) {               // 第一行，word1为空时，word1 转为 word2 的步数，一直添加
            dp[0][j] = j;
        }

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {       // 如果最后一位数相等，那么就不需要进行其他操作了，故此步数不用加一
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1],              // word1替换，可能word1的0~i-1位置与word2的0~j-1位置的字符都相同,只是当前位置的字符不匹配,进行替换操作后两者变得相同, 所以此时dp[i][j]=dp[i-1][j-1]+1(这个加1代表执行替换操作)
                                        Math.min(dp[i - 1][j],         // word1删除，原本 word1[i-1] 到 word2[j] 已经匹配，但此时多了 i 这一步，所以我们要把它删除掉，才能使才能使此时word1的0~i(这个i是执行了删除操作后新的i)和 word2的0~j位置匹配,因此此时dp[i][j]=dp[i-1][j]+1(这个加1代表执行删除操作)
                                                 dp[i][j - 1])) + 1;   // word1新增，若此时word1的0~i位置只是和word2的0~j-1位置匹配,此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得 此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上, 所以此时dp[i][j]=dp[i][j-1]+1(这个加1代表执行插入操作)
                }
            }
        }
        return dp[rows][cols];
    }
}